package com.example.leetcode.prcatice;

/**
 * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
 *
 * <p>
 *
 * <p>示例 1:
 *
 * <p>输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
 */
public class Test518 {

  public int change(int amount, int[] coins) {
    int length = coins.length;
    int[][] dp = new int[length + 1][amount + 1]; // dp[i][j] 代表选择前i个硬币，产生数目的amount的数量
    dp[0][0] = 1;
    for (int i = 1; i <= length; i++) {
      int val = coins[i - 1];
      for (int j = 0; j <= amount; j++) {
        dp[i][j] = dp[i - 1][j];
        for (int k = 1; k * val <= j; k++) {
          dp[i][j] += dp[i - 1][j - k * val];
        }
      }
    }
    return dp[length][amount];
  }

  public int change2(int amount, int[] coins) {
    int length = coins.length;
    int[] dp = new int[amount + 1]; // 数目为amount的数目
    dp[0] = 1;
    for (int coin : coins) {
      for (int i = coin; i <= amount; i++) {
        dp[i] += dp[i - coin];
      }
    }
    return dp[amount];
  }
}

class demo {
  public static void main(String[] args) {
    Test518 test518 = new Test518();
    int[] num = {5, 2, 1};
    System.out.println(test518.change(5, num));
    System.out.println(test518.change2(5, num));
  }
}
 /*
   dp[5] = dp[5] + dp[0] =1
   dp[2] = d[2] + dp[0] = 1

 */
